from util import Counter

class Polynomial:
  """
  A Polynomial object collects all the values which are added, subtracted,
  multiplied or divided into it. It returns a resulting Polynomial of the
  original value.

  >>> import poly
  >>> a = poly.Polynomial(10)
  >>> (a + 5)._Polynomial__coeffs == {0:5, 1: 1.0}
  >>> (5 + a)._Polynomial__coeffs == {0:5, 1: 1.0}
  >>> (a - 5)._Polynomial__coeffs == {0:-5, 1: 1.0}
  >>> (5 - a)._Polynomial__coeffs == {0:5, 1: -1.0}
  >>> str((5+a)*(2+a)/3)
  '0.333333333333x^2 + 2.33333333333x + 3.33333333333'
  >>> str(2/a)
  '2.0x^-1'
  >>> str((2/a) * a)
  '2.0'
  """
  def get_polynomial_coeffs(self):
    return self.__coeffs
  
  def __init__(self, value, coeffs = None):
    """
    value - value of x (used to check that two polynomials are functions
            of the same parameter
    coeffs - the coefficients of the polynomial
    """
    self.__val = value
    if coeffs is None:
       # coefficient of x^1 is 1.0 
      self.__coeffs = Counter({1:1.0})
    else:
      self.__coeffs = Counter(coeffs)
    
    self.__compress()

  def __compress(self):
    # delete coefficients with value 0
    for k in [k for k,v in self.__coeffs.iteritems() if v == 0]:
      del self.__coeffs[k]
      
  def __str__(self):
    ans = ""
    keys = self.__coeffs.keys()
    keys.sort(reverse=True)
    for k in keys:
      if k != 0:
        if float(self.__coeffs[k]) != 1.0:
          coeff = str(self.__coeffs[k])
        else:
          coeff = ""
        if k != 1:
          expo = "^" + str(k)
        else:
          expo = ""
        ans += coeff + "x" + expo + " + "
      else:
        ans += str(self.__coeffs[k]) + " + "
    return ans[:-3]
  
  def __add__(a, b):
    c = Polynomial(a.__val, a.__coeffs)
    if b.__class__ is Polynomial:
      assert(a.__val is b.__val)
      for k,v in b.__coeffs.iteritems():
        c.__coeffs[k] += v
    else:
      c.__coeffs[0] += b

    c.__compress()
    return c

  def __radd__(a,b):
    return a.__add__(b)
  
  def __sub__(a, b):
    c = Polynomial(a.__val, a.__coeffs)
    if b.__class__ is Polynomial:
      assert(a.__val is b.__val)
      for k,v in b.__coeffs.iteritems():
        c.__coeffs[k] -= v
    else:
      c.__coeffs[0] -= b
    
    c.__compress()
    return c

  def __rsub__(a,b):
    if b.__class__ is Polynomial:
      return b.__sub__(a)
    else:
      return Polynomial(a.__val, {0:b}).__sub__(a)
  
  def __mul__(a, b):
    if b.__class__ is Polynomial:
      assert(a.__val is b.__val)
      c = Polynomial(a.__val, Counter())
      for k1, v1 in a.__coeffs.iteritems():
        for k2, v2 in b.__coeffs.iteritems():
          c.__coeffs[k1+k2] += v1 * v2
    else:
      c = Polynomial(a.__val, a.__coeffs)
      c.__coeffs *= b
    
    c.__compress()
    return c

  def __rmul__(a, b):
    return a.__mul__(b)
  
  def __div__(a, b):
    if b.__class__ is Polynomial:
      assert(a.__val is b.__val)
      if len(b.__coeffs) != 1:
        raise TypeError("Division by polynomial requires divisor to have "\
                        + "exactly one non-zero coefficient")
      k1 = b.__coeffs.keys()[0]
      v1 = b.__coeffs[k1]
      c = Polynomial(a.__val, dict((k-k1, v/float(v1)) \
                                   for k,v in a.__coeffs.iteritems()))
    else:
      c = Polynomial(a.__val, a.__coeffs/float(b))
    
    c.__compress()
    return c

  def __rdiv__(a,b):
    if b.__class__ is Polynomial:
      return b.__div__(a)
    else:
      return Polynomial(a.__val, {0:b}).__div__(a)

